
/*单链表（含头结点）*/
#include<stdio.h>
#include<stdlib.h>
 

typedef int ElemType;
 
typedef struct LNode{
	ElemType data;  //数据域
	struct LNode *next;  // 指针域
}LNode,*LinkList;
 
LinkList CreateList1(ElemType a[], int n);  //头插法建立单链表
LinkList CreateList2(ElemType a[], int n); //尾插法创建单链表
void OutputList(LinkList L); //输出单链表全部元素
int Length(LinkList L); //获取单链表长度(不含头结点)
int InsertLNode(LinkList L, int i, ElemType e); //在第i个位置插入结点,即在第i-1个结点之后插入新结点
int DeleteNode(LinkList L, int i, ElemType *e);  //删除第i个结点，并用e返回其值
 
 
void main(){
	LinkList L = NULL;
	ElemType a[] = { 1, 2, 3, 4, 5 };
	ElemType e;
	L = CreateList2(a, 5);
	OutputList(L);
	InsertLNode(L, 6, 6);
	OutputList(L);
	DeleteNode(L, 1, &e);
	printf("%d\n", e);
	OutputList(L);
 
}
 
LinkList CreateList1(ElemType a[], int n){   //头插法建立单链表
	int i;
	LinkList L = NULL, s = NULL;
	L = (LNode*)malloc(sizeof(LNode));
	L->next = NULL;
 
	for (i = 0; i < n; i++){
		s = (LNode*)malloc(sizeof(LNode));
		s->data = a[i];
		s->next = L->next;
		L->next = s;
	}
	return L;
}
 
LinkList CreateList2(ElemType a[], int n){   //尾插法创建单链表
	int i;
	LinkList L = NULL, s = NULL, r = NULL;
	L = (LNode*)malloc(sizeof(LNode));
	L->next = NULL;
	r = L;
	for (i = 0; i < n; i++){
		s = (LNode*)malloc(sizeof(LNode));
		s->data = a[i];
		s->next = NULL;
		r->next = s;
		r = s;  //r指向新的表尾结点
	}
	r->next = NULL;
	return L;
}
// 输出所有链表的思路：
// 1.让头节点的next 指向下一个节点 
// 2. 做一个循环 当超出时打断循环 循环内的时候 p 指向下一个 p 是 现在的节点 p=p-> next 节点会向下一个移动
void OutputList(LinkList L){  //输出单链表全部元素
	LinkList p = L->next;
	while (p){
		printf("%d  ", p->data);
		p = p->next;
	}
	printf("\n");
}
 
int Length(LinkList L){  //获取单链表长度(不含头结点)
	LinkList p = L->next;
	int len = 0;
	while (p){
		len++;
		p = p->next;
	}
	return len;
}
 
int InsertLNode(LinkList L, int i, ElemType e){ //在第i个位置插入结点,即在第i-1个结点之后插入新结点
	if (i<1 || i>Length(L) + 1){
		printf("插入位置错误！\n");
		return -1;
	}
	LinkList p = L;  //p始终指向第i-1个结点
	LinkList s = NULL;
	while (--i){
		p = p->next;
	}
	s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
 
	return 1;
}
 
int DeleteNode(LinkList L, int i, ElemType *e) { //删除第i个结点，并用e返回其值
	if (i<1 || i>Length(L)){
		printf("删除位置错误！\n");
		return -1;
	}
	LinkList p = L; //p指向待删除结点的前驱结点
	LinkList q; //q指向待删除结点
	while (--i){
		p = p->next;
	}
	q = p->next;
	p->next = q->next;
	*e = q->data;
	free(q);
	return 1;
}
